\section{Applications}
\label{sec:parameters}
In this section we apply Theorem~\ref{theorem:complexity1} to various sets of parameters suggested in the literature. In order to compute concrete costs we rely on numerical approximations in various places such as the computation of $p_j$. We used $2n-4n$ bits of precision for all computations, increasing this precision further did not appear to change our results. The solving step for $m$ of Lemma~\ref{lem:m} is accomplished by a simple search implemented in Sage \cite{sagemath}. As a subroutine of this search we rely on numerical integration which we performed using the mpmath library \cite{mpmath} as shipped with Sage. The Sage script used to derive all values in this section is available at \cite{albrecht:bitbucket2012}.

In all cases below we always set $\PrS = 0.99$ and $a := \lceil t\cdot \log_2 n\rfloor$ where $t$ is a small constant, which is consistent with the complexity of the BKW algorithm $q^{\bigO{n/\log_2(n)}} = 2^{\bigO{n}}$ if $q \in \poly$.

\subsection{Regev's Original Parameters}\label{sec:parameters:regev}
In \cite{regev:acm09} Regev proposes a simple public-key encryption scheme with the suggested parameters $q \approx n^2$ and $\alpha = 1/(\sqrt{n} \cdot \log_2^2 n\sqrt{2\pi})$. We consider the parameters in the range $n=32,\dots,256$. In our experiments $t=3.0$ produced the best results, i.e., higher values of $t$ resulted in $m$ growing too fast. Plugging these values into the formulas of Theorem~\ref{theorem:complexity1} we get an overall complexity of 
\begin{comment}
sage: n, m = var('n,m')
sage: assume(n>0)
sage: assume(m>0)
sage: q = n^2
sage: t, d, r = 3, 2, 2
sage: a = t*log(n)
sage: b = n/a
sage: repeat = n/d
sage: corrector = (q**d)/(q**d - 1)
sage: stage1a = (q**b-1)/2.0 * ( a*(a-1)/2.0 * (n+1) - b*a*(a-1)/4.0 - b/6.0 * ( (a-1)**3 + 3/2.0*(a-1)**2 + 1/2.0*(a-1) ) )
sage: stage1b = corrector * (repeat + 1)/2.0 * m * (a/2.0 * (n + 2))
sage: stage1  = stage1a + stage1b
sage: stage2  = repeat * m * q**d
sage: stage3  = (repeat + 1) * d * a * q**b/2.0
sage: nops = stage1 + stage2 + stage3
sage: nops = nops.simplify_full()
sage: num = nops.numerator()
sage: den = nops.denominator()
sage: ops = num.operands()
sage: f = sum(op for op in ops if op >= 0)/den # we throw away things that only make it smaller
sage: f.simplify_full()
\end{comment}
\begin{eqnarray*}
\frac{mn^9 + \frac{1}{6} \, 2^{\frac{2}{3}n} n^5  + {\left[{\left(3\, n + \frac{9}{2}\right)} \cdot \left(2^{\frac{2}{3}n}n^4 + 1\right)\right]} \log_2\left(n\right)^{2} + \frac{1}{6} \, n}{2 \, {\left(n^4 -1\right)}}\\
\end{eqnarray*}
operations in $\Zq$ after simplification.
If $m <2^{(\frac{2}{2.6}n)})$ then this expression is dominated by
$$\frac{\frac{1}{6} n^5 +  {\left(3 \, n^5 + \frac{9}{2}n^4\right)} \cdot \log_2\left(n\right)^2}{2 \, (n^4 - 1)} 2^{\frac{2}{3}n}\in 2^{\frac{2}{3}n + \bigO{\log n}}.$$
However, since we compute $m$ numerically, we have to rely concrete values for various $n$ to verify that with these settings indeed $m$ does not grow too fast. Table~\ref{tab:concrete_regev} lists the estimated number of calls to $\Ldis$ (``$\log_2 \#\Ldis $''), the estimated number of required ring (``$\log_2 \#\Zq $'') and bit (``$\log_2 \#\mathbb{Z}_2 $'')  operations, the costs in terms of ring operations for each of the three stages sampling, hypothesis testing and back substitution.

\begin{table}[!htb]
\begin{center}
\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|} 
\hline
$n$ & $\log_2 m $ & \multicolumn{4}{|c|}{$\log_2 \#\Zq $ in} & $\log_2 \#\mathbb{Z}_2 $ & $\log_2 \#\Ldis $\\
\hline
    &                                & sample & hypo. & subs. & total & & \\
\hline
 32 &  19.93 &  32.76 &  34.94 &  29.31 &  35.25 &  38.57 &  25.64\\
 48 &  28.90 &  43.70 &  45.66 &  40.69 &  46.02 &  49.50 &  35.81\\
 64 &  34.22 &  54.36 &  52.22 &  51.86 &  54.85 &  58.43 &  45.87\\
 80 &  42.19 &  65.50 &  61.16 &  62.94 &  65.78 &  69.44 &  56.60\\
 96 &  49.83 &  76.52 &  69.58 &  73.91 &  76.75 &  80.47 &  67.31\\
112 &  58.79 &  87.51 &  79.22 &  84.84 &  87.72 &  91.49 &  78.02\\
128 &  67.44 &  98.46 &  88.44 &  95.75 &  98.67 & 102.48 &  88.74\\
144 &  76.40 & 109.35 &  97.91 & 106.61 & 109.56 & 113.40 &  99.43\\
160 &  86.37 & 120.23 & 108.34 & 117.46 & 120.43 & 124.30 & 110.12\\
176 &  97.34 & 131.09 & 119.71 & 128.29 & 131.28 & 135.18 & 120.82\\
192 & 106.30 & 141.93 & 129.06 & 139.10 & 142.12 & 146.04 & 131.51\\
208 & 117.27 & 152.76 & 140.37 & 149.91 & 152.95 & 156.89 & 142.20\\
224 & 128.56 & 163.57 & 151.98 & 160.70 & 163.76 & 167.72 & 152.88\\
240 & 139.52 & 174.37 & 163.24 & 171.48 & 174.56 & 178.54 & 163.57\\
256 & 150.49 & 185.17 & 174.49 & 182.26 & 185.35 & 189.35 & 174.25\\
\hline
\end{tabular}
\end{center}
\caption{Cost of solving Search-LWE for parameters suggested in \cite{regev:acm09} with $d=1,t=3,\PrS=0.99$ with BKW.}
\label{tab:concrete_regev}
\end{table}

\subsection{Lindner and Peikert's Parameters}
\label{sec:parameters:pqc}

In \cite{LindnerP10}, Lindner and Peikert propose new attacks and parameters for LWE. Table~\ref{tab:concrete_lp} lists concrete costs of the BKW algorithm for solving LWE under the parameter choices from \cite{LindnerP10} as interpreted in \cite{albrecht-fitzpatrick-cabracas-goepfert-schneider:bitbucket2013}. In our computations $t=2.7$ produced the best results, i.e., higher values of $t$ resulted in $m$ growing too fast.

\begin{table}[!htb]
\begin{center}
\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|} 
\hline
$n$ & $\log_2 m $ & \multicolumn{4}{|c|}{$\log_2 \#\Zq $ in} & $\log_2 \#\mathbb{Z}_2 $ & $\log_2 \#\Ldis $\\
\hline
    &                                & sample & hypo. & subs. & total & & \\
\hline
 32 &   7.64 &  35.91 &  33.65 &  33.92 &  36.46 &  39.78 &  28.84\\
 48 &   9.97 &  45.75 &  36.56 &  43.58 &  46.04 &  49.52 &  37.94\\
 64 &  15.61 &  54.82 &  42.62 &  52.53 &  55.09 &  58.67 &  46.49\\
 80 &  22.25 &  63.39 &  49.58 &  61.02 &  63.65 &  67.31 &  54.66\\
 96 &  30.90 &  71.62 &  58.49 &  69.18 &  71.86 &  75.58 &  62.57\\
112 &  40.86 &  79.57 &  68.68 &  77.08 &  79.81 &  83.58 &  70.25\\
128 &  54.15 &  87.32 &  82.16 &  84.78 &  87.58 &  91.39 &  77.76\\
144 &  37.54 & 102.31 &  67.71 &  99.73 & 102.53 & 106.37 &  92.54\\
160 &  46.51 & 110.38 &  76.83 & 107.77 & 110.60 & 114.47 & 100.43\\
176 &  56.47 & 118.31 &  86.93 & 115.68 & 118.53 & 122.43 & 108.20\\
192 &  70.76 & 126.13 & 101.35 & 123.47 & 126.34 & 130.26 & 115.87\\
208 &  80.73 & 133.84 & 111.43 & 131.15 & 134.05 & 137.99 & 123.44\\
224 &  94.34 & 141.45 & 125.15 & 138.74 & 141.66 & 145.62 & 130.92\\
240 & 109.62 & 148.98 & 140.53 & 146.25 & 149.18 & 153.16 & 138.33\\
256 & 126.23 & 156.42 & 157.24 & 153.68 & 157.96 & 161.96 & 145.67\\
\hline                                                                                                 
\end{tabular}
\end{center}
\caption{Cost of solving Search-LWE for parameters suggested in \cite{LindnerP10} with $d=1,t=2.7, \PrS=0.99$ with BKW.}
\label{tab:concrete_lp}
\end{table}

\subsection{Albrecht et al.'s Polly-Cracker}
\label{sec:parameters:polly}

In \cite{albrecht-farshim-faugere-perret:asiacrypt2011} a somewhat homomorphic encryption scheme is proposed based on the hardness of computing Gröbner bases with noise. Using linearisation the equation systems considered in \cite{albrecht-farshim-faugere-perret:asiacrypt2011} may be considered as LWE instances. Table~\ref{tab:concrete_polly} lists concrete costs for recovering the secret Gröbner basis using this strategy for selected parameters suggested in \cite{albrecht-farshim-faugere-perret:asiacrypt2011}. In Table~\ref{tab:concrete_polly} ``$\lambda$'' is the targeted bit-security level and $n$ the number of variables in the linearised system. We note that we did not exploit the structure of the secret for Table~\ref{tab:concrete_polly}.


\begin{table}[!htb]
\begin{center}
\begin{tabular}{|r|r|r|r||r||r|r|r|r|r|r|r|r|r|} 
\hline
$\lambda $ & $n$ & $q$ & $\alpha$ & $t$ & $\log_2 m $ & \multicolumn{4}{|c|}{$\log_2 \#\Zq $ in} & $\log_2 \#\mathbb{Z}_2 $ & $\log_2 \#\Ldis $\\
\hline
& & &    &              &                 &  sample & hypo. & subs. & total & &\\
\hline
 80 &  136 &   1999 & 0.005582542\dots & 2.2 &  93.58 & 109.40 & 121.59 & 105.71 & 121.59 & 125.04 & 100.23\\ 
    &  231 &  92893 & 0.000139563\dots & 3.4 & 127.23 & 157.47 & 167.09 & 154.40 & 167.09 & 171.13 & 146.54\\
\hline                                                                                                    
128 & 153 &  12227 & 0.002797408\dots & 2.4 &  84.05 & 132.07 & 117.45 & 129.66 & 132.32 & 136.08 & 122.39\\
    & 253 & 594397 & 0.000034967\dots & 3.8 & 100.66 & 175.15 & 146.00 & 171.88 & 175.29 & 179.55 & 163.89\\
\hline
\end{tabular}
\end{center}
\caption{Cost of finding $G \approx \svec$ for parameters suggested in \cite{albrecht-farshim-faugere-perret:asiacrypt2011} with $d=2, \PrS=0.99$.}
\label{tab:concrete_polly}
\end{table}

